|
In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains every ''m''-by-''n'' matrix exactly once. It is a torus because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence, which can be considered a special case where ''n'' is 1 (one dimension). One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given ''m'' and ''n''. It is known that these always exist when ''n'' = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever ''m'' = ''n'' and even (for the odd case the resulting tori cannot be square). 〔 〕 〔 〕 The smallest possible binary "square" de Bruijn torus, depicted above right, denoted as ''(4,4;2,2)2'' de Bruijn torus (or simply as ''B2''), contains all ''2×2'' binary matrices. ==''B2''== Apart from "translation", "inversion" (exchanging ''0''s and ''1''s) and "rotation" (by 90 degrees), no other ''(4,4;2,2)2'' de Bruijn tori are possible - this can be shown by complete inspection of all ''216'' binary matrices (or subset fulfilling constrains such as equal numbers of ''0''s and ''1''s) . 〔 〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「De Bruijn torus」の詳細全文を読む スポンサード リンク
|